#define _CRT_SECURE_NO_WARNINGS 1
#include "hashtable.h"
#include "unordered_map.h"
#include "unordered_set.h"
#include"Bitset.h"
#include"BloomFilter.h"


//void test1()
//{
//	open_hash::HashTable<int, int> ht;
//	int a[] = { 1,111,25,5,7,4,44,6,2 };
//	for (auto e : a)
//	{
//		ht.Insert(make_pair(e, e));
//	}
//
//	auto ret = ht.Find(111);
//	//ret->_kv.first = 11;
//	ret->_kv.second = 11;
//	ht.Erase(111);
//
//	open_hash::HashTable<string,string> dict;
//	dict.Insert(make_pair("sort", "xxx"));
//	dict.Insert(make_pair("insert", "插入"));
//
//	auto pdict = dict.Find("sort");
//	//ret->_kv.first = 11;
//	pdict->_kv.second = "排序";
//
//}
//
//void test2()
//{
//	hash_bucket::HashTable<int, int> ht;
//	int a[] = { 1,111,25,5,7,4,44,6,2 };
//	for (auto e : a)
//	{
//		ht.Insert(make_pair(e, e));
//	}
//	ht.Print();
//	cout << endl;
//
//	ht.Insert(make_pair(14, 14));
//	ht.Insert(make_pair(24, 24));
//	ht.Insert(make_pair(34, 34));
//	ht.Print();
//	cout << endl;
//
//	hash_bucket::HashNode<int, int>* pos = ht.Find(111);
//	cout << pos->_kv.first << endl;
//	cout << endl;
//
//
//	ht.Erase(24);
//	ht.Erase(44);
//	ht.Erase(4);
//	ht.Print();
//	cout << endl;
//
//	hash_bucket::HashTable<string, string> dict;
//	dict.Insert(make_pair("sort", "排序"));
//	dict.Insert(make_pair("left", "xxx"));
//	dict.Insert(make_pair("insert", "插入"));
//	dict.Insert(make_pair("string", "字符串"));
//	dict.Insert(make_pair("bucket", "桶"));
//	dict.Print();
//	cout << endl;
//
//		auto pdict = dict.Find("left");
//		//ret->_kv.first = 11;
//		pdict->_kv.second = "左边";
//		dict.Print();
//		cout << endl;
//	
//		dict.Erase("sort");
//		dict.Print();
//		cout << endl;
//}
void test3()
{
	cyq::unordered_set<int> s;
	s.insert(1);
	s.insert(2);
	s.insert(3);
	s.insert(4);
	s.insert(5);
	cyq::unordered_set<int>::iterator its = s.begin();
	while (its != s.end())
	{
		//key不能修改
		//(*its)+=1;
		cout << *its << " ";
		++its;
	}
	cout << endl;

	cyq::unordered_map<string,string> m;
	m.insert(make_pair("sort", "排序"));
	m.insert(make_pair("insert", "插入"));
	m.insert(make_pair("erase", "删除"));
	m.insert(make_pair("find", "查找"));
	m.insert(make_pair("modify", "修改"));
	for (auto& kv : m)
	{
		cout << kv.first << ":" << kv.second<<" ";
	}
	cout << endl;

	cyq::unordered_map<string,string>::iterator itm = m.begin();
	while (itm != m.end())
	{
		//key不能修改
		//itm->first += 'x';
		itm->second += 'x';
		cout << (*itm).first<<":"<<(*itm).second << " ";
		++itm;
	}
	cout << endl;

	cyq::unordered_map<string, string> mm(m);
	//mm = m;
	mm.print();

}

void test4()
{
	cyq::unordered_map<string, string> m;
	m.insert(make_pair("sort", "xxx"));
	m.insert(make_pair("sort", "xxxxxxx"));
	m["sort"] = "排序";
	m["insert"] = "插入";
	m["left"];
	for (auto& kv : m)
	{
		cout << kv.first << ":" << kv.second << " ";
	}
	cout << endl;

}

void test5()
{
	string a[] = { "西瓜","哈密瓜","哈密瓜", "哈密瓜", "哈密瓜", "哈密瓜","西瓜","苹果","苹果" ,"苹果","哈密瓜" };
	cyq::unordered_map<string, int> countMap;
	for (const auto& e : a)
	{
		countMap[e]++;
	}

	for (const auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}

}

void test6()
{

	cyq::bitset<-1> bt;
	//cyq::bitset<0xffffffff> bt;
	bt.set(10);
	bt.set(100);
	bt.set(10000);

	cout << bt.test(10) << endl;
	cout << bt.test(100) << endl;
	cout << bt.test(10000) << endl;
	cout << bt.test(999) << endl << endl;

	bt.reset(10);
	cout << bt.test(10) << endl;
	cout << bt.test(100) << endl;
	cout << bt.test(10000) << endl;
	cout << bt.test(999) << endl ;
}

//出现一次的数字
void test7()
{
	int a[] = { 1,1,1,2,2,2,3,4,4,4,4,4,5,5,5,6,7,7,8,9 };
	cyq::twobitset<10> tbs;
	for (auto e : a)
	{
		tbs.set(e);
	}

	for (auto e : a)
	{
		if (tbs.is_once(e))
		{
			cout << e << " ";
		}

	}
	cout << endl;
}

//求交集
void test8()
{
	int a[] = { 1,1,1,2,2,2,3,4,4,4,4,4,5,5,5,6,7,7,8,9 };
	int a1[] = { 8,8,8,8,4,4,4,4,4,4,1,1 };
	cyq::bitset<10> bs;
	for (auto e : a)
	{
		bs.set(e);
	}

	cyq::bitset<10> bs1;
	for (auto e : a1)
	{
		bs1.set(e);
	}

	for (int i = 0; i < 10; i++)
	{
		if (bs.test(i) && bs1.test(i))
		{
			cout << i << " ";
		}
	}
	cout << endl;


}

//布隆过滤器
void TestBloomFilter1()
{
	cyq::BloomFilter<100> bf;
	bf.Set("猪八戒");
	bf.Set("孙悟空");
	bf.Set("沙悟净");
	bf.Set("哪吒");

	cout << bf.Test("猪八戒") << endl;
	cout << bf.Test("孙悟空") << endl;
	cout << bf.Test("沙悟净") << endl;
	cout << bf.Test("哪吒") << endl;
	cout << bf.Test("二郎神") << endl;



}

void TestBloomFilter2()
{
	srand(time(0));
	const size_t N = 100000;
	cyq::BloomFilter<N * 8> bf;

	std::vector<std::string> v1;
	std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
	//std::string url = "猪八戒";

	for (size_t i = 0; i < N; ++i)
	{
		v1.push_back(url + std::to_string(i));
	}

	for (auto& str : v1)
	{
		bf.Set(str);
	}

	// v2跟v1是相似字符串集（前缀一样），但是不一样
	std::vector<std::string> v2;
	for (size_t i = 0; i < N; ++i)
	{
		std::string urlstr = url;
		urlstr += std::to_string(9999999 + i);
		v2.push_back(urlstr);
	}

	size_t n2 = 0;
	for (auto& str : v2)
	{
		if (bf.Test(str)) // 误判
		{
			++n2;
		}
	}
	cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;

	// 不相似字符串集
	std::vector<std::string> v3;
	for (size_t i = 0; i < N; ++i)
	{
		string url = "zhihu.com";
		//string url = "孙悟空";
		url += std::to_string(i + rand());
		v3.push_back(url);
	}

	size_t n3 = 0;
	for (auto& str : v3)
	{
		if (bf.Test(str))
		{
			++n3;
		}
	}
	cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}



int main()
{
	//test1();

	//test2();

	test3();
	cout << "------------------------------------------------------------" << endl;

	test4();
	cout << "------------------------------------------------------------" << endl;

	test5();
	cout << "------------------------------------------------------------" << endl;

	test6();
	cout << "------------------------------------------------------------" << endl;

	test7();
	cout << "------------------------------------------------------------" << endl;

	test8();
	cout << "------------------------------------------------------------" << endl;

	TestBloomFilter1();
	cout << "------------------------------------------------------------" << endl;

	TestBloomFilter2();
	cout << "------------------------------------------------------------" << endl;

	return 0;
}